Curso de ScriptVox Intermedirio - Aula 7 - Prof. Oswaldo Vernet - iNCE/UFRJ

Talvez a principal novidade nesta verso 6.0 do interpretador ScriptVox tenha sido
a introduo de trs novos tipos de dados, alm do tipo cadeia, que era o nico 
suportado at ento na linguagem.

O tipo revela a natureza do dado e est intimamente relacionado ao conceito matemtico 
de conjunto: se um dado tem determinado tipo, isto quer dizer que ele  um elemento 
do conjunto constitudo por todos os dados daquele tipo.

Assim, por exemplo, se uma varivel armazena um valor inteiro, ela armazena um certo
elemento do conjunto de nmeros inteiros que podem ser manipulados na linguagem.
 claro que, computacionalmente, existe um limite na representao interna dos dados,
e o conjunto dos inteiros em uma determinada linguagem no coincide com o conjunto 
dos nmeros inteiros em matemtica, porque este ltimo  infinito.

Numa linguagem como C ou Java, precisamos DECLARAR variveis antes de us-las e, 
no ato da declarao, informamos ao compilador o tipo de dados que ela pode armazenar.
Isto significa que, enquanto aquela varivel durar, ela s armazenar dados daquele tipo. 
Se for declarada como inteira, s poder armazenar nmeros inteiros; se for declarada como 
cadeia, s poder armazenar cadeias; e assim por diante.

Em diversas linguagens interpretadas, as variveis no precisam ser declaradas: 
uma varivel  criada no momento exato em que ela  mencionada pela primeira vez.
Quando uma varivel tem seu contedo modificado, o dado que est sendo atribudo a ela
 de determinado tipo e, enquanto a varivel armazenar este dado, diremos que a varivel 
 tambm daquele tipo. Assim, aps a seguinte atribuio:

x := "uma frase no muito longa"

a varivel "x" ser do tipo CADEIA, porque ela armazenar, at segunda ordem, a cadeia
"uma frase no muito longa". Se, em outro ponto posterior da execuo do script, fizermos 
a seguinte atribuio:

x := 2

a varivel "x" deixar de ser do tipo CADEIA e passar a ser do tipo INTEIRO, porque,
a partir de agora, e at segunda ordem, o valor que ela armazena  inteiro.

Pelo fato de as variveis herdarem os tipos dos contedos que armazenam, a tipagem em
ScriptVox  dita DINMICA. O mesmo acontece em outras linguagens interpretadas,
como PHP, Python e Javascript.

At este ponto do curso, j examinamos dois TIPOS suportados pelo ScriptVox: INTEIRO e
CADEIA. Vamos, nesta aula, estudar o tipo LISTA.

O texto que se segue  uma obra de fico. Qualquer semelhana com a realidade  mera
coincidncia.

Mame quer ir ao mercado fazer compras e pede a seu filho que tome nota, num pedacinho
de papel, dos itens a serem comprados. O filho, bom aluno de computao e acostumado 
tarefa que se repete toda semana, percebe logo que mame deseja construir uma LISTA de 
coisas a comprar. Esta lista comear vazia, sem nenhum item, at que mame pronuncie 
o primeiro item a ser comprado. 

Mame comea ento: 

"arroz, feijo, alho, cebola, patinho cortado pra bife, tomate, chuchu."

O que o filho faz?  Vai escrevendo uma linha depois da outra no seu pedacinho de papel,
enquanto mame vai ditando. Cada item que mame fala vai para o ltimo lugar da lista. 

O filho interrompe: 

"Me, pra que comprar chuchu?  No tem gosto de nada."

Mame ignora completamente a interveno, olha na cesta e verifica que tem alho de sobra. 
Ento, manda o filho riscar o alho da lista. 

Depois desta excluso, mame pergunta:
 
"Meu anjo, eu j falei cebola?".

O filho, de pronto, responde: 

"Falou, me, cebola  o quarto item".

Mame ento continua:

"Bom, cebola eu j falei. E qual foi o segundo item que eu ditei?"

O filho examina e lista e responde:

"Foi feijo, me".

E mame muda de ideia:

"Em vez de feijo, troca o segundo item por lentilha, seu pai disse que t com saudade de
comer lentilha". 

O filho faz uma careta, porque detesta lentilha. Mas cumpre a ordem da me e troca "feijo" 
por "lentilha". Mame finaliza: 

"espinafre, abbora, carne moda". E pronto. 

Para conferir, mame pede a seu filho que diga tudo o que vai ser comprado. O rapaz,
ento, l tudo o que escreveu no papelzinho, na ordem que mame ditou; menos o alho,
que foi retirado e o feijo que foi trocado por lentilha. Assim:

arroz, lentilha, cebola, patinho cortado pra bife, tomate, chuchu, espinafre, abbora, carne moda.

A mame reclama: 

"Menino, assim eu fico doida no mercado! Bota as coisas em ordem: carne perto de carne, legume
perto de legume, seno fico zanzando igual uma barata tonta". 

O filho obediente atende, rearrumando os itens da seguinte maneira: 

arroz, lentilha, patinho cortado pra bife, carne moda, cebola, tomate, chuchu, espinafre, abbora.

A mame pergunta: 

"Falei cheiro verde?" 

O filho examina a lista e diz: 

"No, mame, cheiro verde no t na lista no". 

Mame ordena: 

"Ento bota cheiro verde, mas v se bota no lugar certo". 

O filho, intrigado, indaga: 

"E tem lugar certo do cheiro verde?".  

Mame, irritada, responde: 

"Claro que tem, peste:  depois da cebola, porque a banca do cheiro verde fica logo depois da banca da cebola".

E a lista final de compras fica assim: 

arroz, lentilha, patinho cortado pra bife, carne moda, cebola, cheiro verde, tomate, chuchu, espinafre, abbora.

O filho, por ltimo, pergunta: 

"Me, e as quantidades de casa coisa? Voc nunca diz."

Mame silencia por alguns segundos, reflete e retruca: 

"Isso no  receita, seu lesado, isso  lista de compras. Quantidade a gente bota na receita".

Sem discutir, o filho entrega o papelzinho a mame e corre pro computador, para tuitar que j fez a lista
de compras da semana e que mame s diz quantidades em receitas. 1191 comentam.

Apesar de ingnuo, o dilogo ilustra aproximadamente o que se entende, do ponto de vista computacional,
por uma LISTA SEQUENCIAL. Uma lista sequencial (que aqui chamaremos apenas de LISTA)  uma estrutura 
constituda por posies consecutivas, que so ocupadas por elementos. 

A LISTA VAZIA  aquela que no tem nenhuma posio ocupada. Se uma lista tem elementos, ela no  vazia,
e dizemos que ela est POVOADA. Numa lista povoada, no podem existir posies vagas: o primeiro elemento 
 seguido do segundo, que  seguido do terceiro, e assim sucessivamente, at o ltimo elemento da lista. 
Portanto, numa lista povoada, no pode haver buracos: se existem o primeiro e o terceiro elementos, 
obrigatoriamente entre eles deve existir o segundo.

O dilogo tambm ilustra as operaes que costumamos efetuar sobre listas.

Quando mame pede ao filho que tome nota, ele parte de uma folha em branco, sem nenhum item.
Isto corresponde  operao de PRODUZIR UMA LISTA VAZIA, sem elementos.

Quando mame dita os itens e o filho os acrescenta ao final da lista, isto corresponde a
ANEXAR elementos ao final da lista.

Quando mame pergunta qual foi o segundo item ditado, isto corresponde a INDEXAR a lista,
obtendo o elemento armazenado em uma certa posio.

Pode ser necessrio verificar se um determinado item j foi ou no includo na lista,
ou seja, sele ele PERTENCE  lista. Isto corresponde a BUSCAR um elemento na lista e a resposta
pode ser SIM ou NO. No caso da resposta positiva (ou seja, o elemento pertence  lista),  usual
informar tambm em que posio ele est armazenado; assim, alm de sabermos que o elemento est
na lista, ficamos sabendo onde ele est.

Quando mame pede ao filho que leia tudo o que ela j ditou, isto corresponde a PERCORRER a
lista, executando uma determinada ao para cada elemento. No caso, a ao  FALAR cada elemento. 

Quando mame mandou riscar o alho, pois j havia de sobra em casa, o que o filho fez, na verdade, 
foi verificar em que posio da lista estava o elemento "alho". Conhecida esta posio, ele 
moveu todos os elementos das posies seguintes de uma posio para trs, mas sem tirar da ordem. 
Portanto, este desejo de mame correspondeu a duas operaes sobre a lista: uma BUSCA, para 
saber em qual posio est o elemento, seguida de uma REMOO, que consiste em retirar 
o elemento de uma certa posio da lista e mover os seguintes de uma posio para trs,
para no deixar buracos.

Por fim, mame manda o filho acrescentar o cheiro verde  lista de compras na posio seguinte
 posio em que se encontra a cebola. Isto corresponde a BUSCAR o elemento "cebola", descobrindo
sua posio, e depois INSERIR "cheiro verde" na posio seguinte. Para isto, o elemento daquela
posio os das posies seguintes e devem ser movidos de uma posio para frente, de modo a
abrir espao para o elemento que vai entrar.

O nico detalhe que no est presente neste dilogo  que, computacionalmente, uma lista pode
conter elementos repetidos. Isto numa lista de compras talvez no faa muito sentido; mas uma
lista constituda por informaes em um script pode conter repeties.

Vejamos, ento, em ScriptVox, como trabalhar com listas. 

Por analogia com outras linguagens de programao, convencionamos que as posies em uma
lista comeam de 0, diferentemente das cadeias, em que o primeiro caractere est na posio 1.
Assim, o primeiro elemento de uma lista  o da posio 0, o segundo elemento  o da posio 1, 
e assim por diante. 

O tamanho (ou cardinalidade) de uma lista  o nmero de elementos armazenados nela. Portanto, a
lista vazia tem tamanho zero e, se uma lista povoada tem tamanho N, sabemos que as posices de 
zero at N menos 1 esto ocupadas por elementos.

Vamos enumerar, a seguir, algumas aes sobre listas:

1. A lista vazia  simbolizada por um abre colchete seguido de um fecha colchete, sem nenhum
   elemento entre eles. Assim, se quisermos produzir a lista vazia e atribu-la  varivel 
   "itens", usamos a seguinte atribuio:
   
   itens := []
   
2. Se quisermos produzir uma lista e j conhecemos os elementos a serem guardados nela, basta
   coloc-los por ordem de posio entre o abre e o fecha colchetes, separados por vrgulas, 
   como no exemplo:
   
   itens := [ "arroz", "vinagre", "cebola", "alho" ]
   
   Aps esta atribuio, o contedo da varivel "itens" ser uma lista constituda por quatro
   elementos, todos eles cadeias. O elemento da posio zero  a cadeia "arroz", o da posio
   1  "vinagre", o da posio 2  "cebola" e o da posio 3  "alho". Esta lista tem tamanho 4,
   estando ocupadas as posies de 0 a 3, sem buracos.
   
3. Se desejamos saber qual o elemento da posio 2, basta mencionarmos

   x := itens[2]
   
   No nosso exemplo, a varivel "x" conter, aps a atribuio, a cadeia "cebola".
   
   Observe que a sintaxe  a mesma usada para indexar cadeias. O ndice pode ser qualquer expresso
   que tenha como resultado um nmero inteiro entre 0 e o tamanho da lista menos um.
   
4. Para substituir o elemento em uma dada posio da lista por outro valor, basta usarmos a
   indexao do lado esquerdo do sinal de atribuio:
   
   itens[2] := "cominho"
   
   No exemplo, a varivel "itens" passaria a conter a lista
   
   [ "arroz", "vinagre", "cominho", "alho" ]
   
   aps esta atribuio. Da mesma forma, o ndice utilizado entre colchetes deve ser uma expresso 
   que tenha como resultado um nmero inteiro entre 0 e o tamanho da lista menos um.
   
5. Para anexar um elemento ao final da lista, aumentando em uma unidade o seu tamanho, no 
   preciso especificar o ndice do lado esquerdo da atribuio; basta abrir e fechar colchetes. Assim:
   
   itens[] := "leite"
   
   tem o efeito de acrescentar a cadeia "leite" ao final da lista, que passa a ter, ento, 5 elementos:
   
   [ "arroz", "vinagre", "cominho", "alho", "leite" ]
   
6. Se a questo  descobrir a posio que um certo elemento ocupa na lista, a mesma funo POS, que
   estudamos para cadeias, serve tambm para listas, mas com uma diferena: quando o elemento no
   estiver na lista, a funo retornar menos um, em vez de zero, j que zero, para listas,  uma
   posio vlida. Assim

   p := POS ("alho", itens)

   vai atribuir  varivel "p" o inteiro 3, j que a cadeia "alho" est na posio 3 da lista
   armazenada em "itens". Porm, se o comando fosse:

   p := POS ("banana", itens)

   a varivel "p" teria o valor menos um aps a atribuio. O inteiro menos um no corresponde a
   nenhuma posio vlida da lista e isto significa que o elemento "banana"  no pertence a ela.

7. Para remover o elemento de uma dada posio em uma lista, usamos a funo RETIRA, passando como
   parmetros a lista e a posio. Assim:

   RETIRA (itens, 1)
   
   A funo modifica a prpria lista passada como primeiro parmetro, excluindo dela o elemento da
   posio passada como segundo parmetro. Vale lembrar que os elementos das posies seguintes
   so movidos de uma posio para trs, de modo que lista continue ntegra, sem buracos. Aps esta
   chamada, no nosso exemplo, a varivel "itens" conter a lista:
   
   [ "arroz", "cominho", "alho", "leite" ]
   
   Repare que o elemento "vinagre", que ocupava a posio 1, foi removido.
   
8. Para acrescentar um elemento em uma dada posio da lista, a funo INSERE espera como parmetros
   a lista, a posio e o elemento a ser acrescentado, nesta ordem. O que ela faz  mover todos os
   elementos a partir da posio dada (e inclusive o elemento situado nela) de uma posio para frente,
   abrindo espao para adicionar o elemento dado como terceiro parmetro. Este elemento ficar
   exatamente na posio indicada pelo segundo parmetro. Assim, se usarmos a chamada:

   INSERE (itens, 2, "organo")

   a lista armazenada na varivel "itens" ter o seguinte contedo:

   [ "arroz", "cominho", "organo", "alho", "leite" ]

   O novo elemento "organo" ficou exatamente na posio 2 da lista e o elemento antigo que ocupava
   a posio 2 (no caso, "alho") e o seguinte ("leite") foram movidos de uma posio para frente.   

9. A funo TAMANHO (a mesma usada para cadeias) pode tambm ser aplicada a uma lista, quando
   desejamos obter o nmero de elementos nela armazenados. Assim, seguindo o exemplo, se usarmos o comando:
   
   escreve TAMANHO(itens)
   
   ser escrito, na tela, o inteiro 5.
   
  

EXERCCIOS

Perguntas de Estudo Dirigido

1.  Defina, com suas palavras, o que  uma lista.
2.  D um exemplo de lista, na vida quotidiana, em que elementos podem estar repetidos.  
3.  Como se produz uma lista vazia?
4.  Como se anexa um elemento ao final de uma lista?
5.  Como se verifica se um elemento pertence ou no a uma lista?
6.  O que signifca PERCORRER uma lista?
7.  Por que alguns elementos precisam ser movidos numa operao de insero ou de remoo em
    uma lista?
8.  Se mame pedisse ao filho: "Confere a se eu coloquei sal. Se no coloquei, acrescenta".
    Como voc executaria este pedido com as operaes que estudamos sobre listas?
9.  Uma cadeia  um caso particular de lista?  Se isto for verdade, ento reflita: 
    quais so os elementos de uma cadeia?


Exerccio de programao

Escreva em ScriptVox e execute no interpretador o script que implementa exatamente a historinha 
entre mame e seu filho, excluindo,  claro, as partes que no se referem  lista 
(por exemplo, o garoto no gostar de chuchu).

Comece com a lista vazia e v traduzindo, em ScriptVox, as ordens de mame. A cada ordem cumprida,
escreva na tela a lista do jeito que ela ficou. Use o comando escreve (ele sabe escrever listas).


Exerccio de avaliao (enviar para scriptvox@gmail.com at o meio-dia de 9 de fevereiro de 2012)

Sua tarefa ser implementar um script para manipular uma lista atravs de comandos digitados
pelo usurio.

O script inicia com uma lista vazia, guardada em alguma varivel. O usurio digita comandos,
que so lidos pelo seu script, e esses comandos realizam operaes sobre a lista.

Cada comando digitado pelo usurio  constitudo por um verbo no imperativo, que indica o comando,
seguido de um complemento, que  sempre um elemento. Entre o verbo e o complemento
pode haver um nmero qualquer de brancos. O script termina quando o usurio tecla enter na
hora de digitar a linha de comando.

Implemente apenas trs comandos:

1. ANEXA elemento
   O elemento digitado logo aps o comando ANEXA deve ser anexado ao final da lista.
   
2. BUSCA elemento
   Obtm a posio do elemento na lista, caso ele pertena  lista. Se no pertencer, dever
   ser escrito na tela: "O elemento no pertence  lista".
   
3. RETIRA elemento
   O elemento deve ser buscado e retirado da lista.
   
Para facilitar a sua vida na hora de quebrar uma linha em verbo e complemento, utilize a
funo nativa "SEPARA", que funciona da seguinte maneira: ela espera como parmetro uma cadeia
e retorna como resultado uma lista contendo as palavras encontradas na cadeia. Por exemplo,
sejam as duas atribuies seguintes:

le linha
palavras := SEPARA (linha)

A varivel "linha" armazena a linha digitada pelo usurio. Suponhamos que ele tenha digitado

RETIRA salsa

Aps a segunda atribuio, a varivel "palavras" ter como contedo a lista 

[ "RETIRA", "salsa" ]

em que o elemento da posio zero  o verbo e o elemento da posio 1  o elemento.

Antes de ler o prximo comando, escreva na tela o contedo atual da lista. E tenha cuidado com
usurios maldosos, que digitam comandos errados ou digitam comandos certos sem especificar
o elemento. No confie em usurios.

Bom estudo!

Oswaldo Vernet







